#ifndef _MATRIX_
#define _MATRIX_

#include <string>
#include <vector>

using namespace std;

class Matrix {
private:
    /* data */
public:
    Matrix( /* args */ ) {}
    ~Matrix() {}
    /* 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。*/
    bool exist( vector< vector< char > >& board, string word ) {
        m_row = board.size();
        if ( m_row <= 0 ) {
            return false;
        }
        m_col = board.front().size();
        if ( m_col <= 0 ) {
            return false;
        }

        if ( word.size() > m_col * m_row ) {
            return false;
        }

        m_status.resize( m_row * m_col );

        for ( size_t i = 0; i < m_row; i++ ) {
            for ( size_t j = 0; j < m_col; j++ ) {

                for ( size_t i = 0; i < m_row * m_col; i++ ) {
                    m_status.at( i ) = false;
                }

                if ( dfsExist( board, word, 0, i, j ) ) {
                    return true;
                }
            }
        }

        return false;
    }
    /* 剑指 Offer 29. 顺时针打印矩阵 */
    vector< int > spiralOrder( vector< vector< int > >& matrix ) {

        if ( matrix.size() == 0 || matrix[ 0 ].size() == 0 ) {
            return vector< int >();
        }
        size_t rowMin = 0, rowMax = matrix.size() - 1;
        size_t colMin = 0, colMax = matrix[ 0 ].size() - 1;

        size_t size = ( rowMax + 1 ) * ( colMax + 1 );

        vector< int > ans;
        size_t           i = 0, j = 0;
        int           status = 1;

        while ( ans.size() < size ) {
            ans.push_back( matrix[ i ][ j ] );
            switch ( status ) {
            case 1: {
                if ( i == rowMin && j < colMax ) {
                    j++;
                    if ( j == colMax ) {
                        rowMin++;
                        status = 2;
                    }
                    break;
                }
            }
            case 2: {
                if ( i < rowMax && j == colMax ) {
                    i++;
                    if ( i == rowMax ) {
                        colMax--;
                        status = 3;
                    }
                    break;
                }
            }
            case 3: {
                if ( i == rowMax && j > colMin ) {
                    j--;
                    if ( j == colMin ) {
                        rowMax--;
                        status = 4;
                    }
                    break;
                }
            }
            case 4: {
                if ( i > rowMin && j == colMin ) {
                    i--;
                    if ( i == rowMin ) {
                        colMin++;
                        status = 1;
                    }
                    break;
                }
            }
            default:
                break;
            }
        }

        return ans;
    }

protected:
    bool dfsExist( vector< vector< char > >& board, string word, unsigned charPos, size_t i, size_t j ) {

        if ( i < 0 || j < 0 || i >= m_row || j >= m_col ) {
            return false;
        }
        else if ( m_status[ i * m_col + j ] || board[ i ][ j ] != word[ charPos ] ) {
            return false;
        }
        else {
            m_status[ i * m_col + j ] = true;
            if ( ( charPos + 1 ) == word.size() ) {
                return true;
            }
            // right -> down -> left -> up
            bool result = dfsExist( board, word, charPos + 1, i, j + 1 ) || dfsExist( board, word, charPos + 1, i + 1, j ) || dfsExist( board, word, charPos + 1, i, j - 1 )
                          || dfsExist( board, word, charPos + 1, i - 1, j );

            if ( !result ) {
                m_status[ i * m_col + j ] = false;
            }

            return result;
        }
    }

private:
    size_t m_row;
    size_t m_col;

    vector< bool > m_status;
};

#endif /*_MATRIX_*/